/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-10-23
 * Time:21:55
 */
//设计循环队列 / 环形队列
//循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
//循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间，
//但是使用循环队列，我们能使用这些空间去存储新的值。
//该类中支持以下的操作：
//MyCircularQueue(k): 构造器，设置队列长度为 k 。
//Front: 从队首获取元素。如果队列为空，返回 -1 。
//Rear: 获取队尾元素。如果队列为空，返回 -1 。
//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
//isEmpty(): 检查循环队列是否为空。
//isFull(): 检查循环队列是否已满。

//基于数组实现
public class MyCircularQueue {
    public int[] elem;
    public int front; //标记队头元素
    public int rear;  //标记队尾元素

    public MyCircularQueue(int k) {
        elem = new int[k+1]; //是k+1的原因:在判满的时候，采取浪费一个空间的做法，例如要设置的队列长度是3，那需要设置长度为4，确保浪费一个空间
    }

    //判断队列是否已满 - 判满采取 浪费一个空间/保留一个位置 的做法
    public boolean isFull() {
        return (rear+1) % elem.length == front;//如果rear下一个位置是等于front，则代表已经满了
    }

    //判断队列是否为空 - 如果rear和front位置相同，代表是空的(只要位置相同就代表空，无论它们在队列的哪一个下标位置)
    public boolean isEmpty() {
        return rear == front;
    }

    //向循环队列插入元素(队尾插入) - 入队列
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear+1)%elem.length;//rear往后走
        return true;
    }

    //从循环队列中删除一个元素(队头删除) - 出队列
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front+1)%elem.length;//采用头删法，front直接往后走，无需担心原来front位置上的元素没有真正删除，它最终会被覆盖掉
        return true;
    }

    //从队头获取元素/获取队头元素
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    //获取队尾元素
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1;//由于队列是一个环，那么需要解决当尾元素在0下标位置时
        return elem[index];
    }
}
